{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Employee Importance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getImportance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #员工的重要性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个保存员工信息的数据结构，它包含了员工 <strong>唯一的 id </strong>，<strong>重要度 </strong>和 <strong>直系下属的 id </strong>。</p>\n",
    "\n",
    "<p>比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 <strong>并不是直系</strong> 下属，因此没有体现在员工 1 的数据结构中。</p>\n",
    "\n",
    "<p>现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>\n",
    "员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个员工最多有一个<strong> 直系 </strong>领导，但是可以有多个 <strong>直系 </strong>下属</li>\n",
    "\t<li>员工数量不超过 2000 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [employee-importance](https://leetcode.cn/problems/employee-importance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [employee-importance](https://leetcode.cn/problems/employee-importance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,5,[2,3]],[2,3,[]],[3,3,[]]]\\n1', '[[1,2,[5]],[5,-3,[]]]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        d = {}\n",
    "        for e in employees:\n",
    "            d[e.id] = e\n",
    "        if id not in d:\n",
    "            return 0\n",
    "        re = 0\n",
    "        l = [id]\n",
    "        while l:\n",
    "            temp = l.pop(0)\n",
    "            re += d[temp].importance\n",
    "            for s in d[temp].subordinates:\n",
    "                l.append(s)\n",
    "        return re\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:        \n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        res=0\n",
    "        def getRes(employees, id) -> int:\n",
    "            nonlocal res\n",
    "            for e in employees:\n",
    "                if id==e.id:\n",
    "                    res+=e.importance\n",
    "                    for val in e.subordinates:\n",
    "                        getRes(employees, val)\n",
    "            return\n",
    "            \n",
    "        getRes(employees,id)\n",
    "        return res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hash_importance = {}\n",
    "        for emp in employees:\n",
    "            hash_importance[emp.id] = [emp.importance, emp.subordinates]\n",
    "\n",
    "        def getSubImportance(id):\n",
    "            score = hash_importance[id][0]\n",
    "            for sub_id in hash_importance[id][1]:\n",
    "                score+=getSubImportance(sub_id)\n",
    "            return score\n",
    "        return getSubImportance(id)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {e.id: e for e in employees}\n",
    "        q = collections.deque([id])\n",
    "        ret = 0\n",
    "        while q:\n",
    "            e = mp[q.popleft()]\n",
    "            ret += e.importance\n",
    "            for sub in e.subordinates:\n",
    "                q.append(sub)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        if len(employees) == 0:\n",
    "            return 0\n",
    "        inf = {}\n",
    "        for emp in employees:\n",
    "            inf[emp.id] = emp\n",
    "        return self.dfs(id,inf)\n",
    "\n",
    "\n",
    "    def dfs(self,id, info):\n",
    "        cur = info[id]\n",
    "        cursum = cur.importance\n",
    "        for curd in cur.subordinates:\n",
    "            cursum += self.dfs(curd, info)\n",
    "        return cursum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        p=None\n",
    "        for e in employees:\n",
    "            if e.id==id:\n",
    "                p=e\n",
    "                break\n",
    "        res=p.importance\n",
    "        c=p.subordinates\n",
    "        for i in c:\n",
    "            res+=self.getImportance(employees,i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        for i in employees:\n",
    "            if i.id==id:\n",
    "                v=i\n",
    "                break\n",
    "        res=v.importance\n",
    "        arr=v.subordinates\n",
    "        for i in arr:\n",
    "            res+=self.getImportance(employees,i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        employee_dict = {}\n",
    "        for employee in employees:\n",
    "            if employee.id not in employee_dict:\n",
    "                employee_dict[employee.id] = [employee.importance, employee.subordinates]\n",
    "        \n",
    "        queue = deque([id])\n",
    "        result = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if cur in employee_dict:\n",
    "                    result += employee_dict[cur][0]\n",
    "                    queue.extend(employee_dict[cur][1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        \"\"\"\n",
    "        locate the employee by input id\n",
    "        get his/her importance val\n",
    "        get the list of subordinates\n",
    "        iterate over the list to get every importance val\n",
    "        \"\"\"\n",
    "        total_importance = 0\n",
    "        employeeIDs = [id]\n",
    "        # find main employee, get subordinate list, add importance\n",
    "        while employeeIDs:\n",
    "            for employee in employees:\n",
    "                if employee.id in employeeIDs:\n",
    "                    employeeIDs.remove(employee.id)\n",
    "                    employeeIDs += employee.subordinates\n",
    "                    total_importance += employee.importance\n",
    "        return total_importance\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {}\n",
    "        score = {}\n",
    "        for i in range(len(employees)):\n",
    "            idd = employees[i].id\n",
    "            imp = employees[i].importance\n",
    "            sub = employees[i].subordinates\n",
    "            mp[idd] = sub\n",
    "            score[idd] = imp\n",
    "        \n",
    "        \n",
    "        res = score[id]\n",
    "        queue = collections.deque([id])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for nxt in mp[node]:\n",
    "                queue.append(nxt)\n",
    "                res += score[nxt]\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        for e in employees:\n",
    "            if e.id == id:\n",
    "                employee = e\n",
    "                break\n",
    "        ans = employee.importance\n",
    "        for sub in employee.subordinates:\n",
    "            ans += self.getImportance(employees, sub)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        record={employee.id:employee for employee in employees}\n",
    "\n",
    "        def dfs(idx):\n",
    "            employee=record[idx]\n",
    "            total=employee.importance+sum(dfs(subIdx) for subIdx in employee.subordinates)\n",
    "            return total\n",
    "        \n",
    "        return dfs(id)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {employee.id: employee for employee in employees}\n",
    "        def dfs(idx):\n",
    "            employee = mp[idx]\n",
    "            if employee.id == -1:\n",
    "                return 0\n",
    "            employee.id = -1\n",
    "            ans = employee.importance\n",
    "            for i in employee.subordinates:\n",
    "                ans += dfs(i)\n",
    "            return ans\n",
    "        return dfs(id)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        dict_ = {employee.id: employee for employee in employees}\n",
    "        imp = []\n",
    "        def search(emp):\n",
    "            if emp is not None:\n",
    "                imp.append(emp.importance)\n",
    "            for i in emp.subordinates:\n",
    "                search(dict_[i])\n",
    "        search(dict_[id])\n",
    "        return sum(imp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        sum = 0\n",
    "        if employees == []:\n",
    "            return 0\n",
    "        sortedById = lambda emp_list, id: sorted(emp_list, key=lambda x: x.id != id)\n",
    "        # employees.sort(key=lambda x: x[0] != id)\n",
    "        employees = sortedById(employees, id)\n",
    "        if employees[0].id != id:\n",
    "            return 0\n",
    "        subs = employees[0].subordinates\n",
    "        sum += employees[0].importance\n",
    "        if subs == []:\n",
    "            return sum\n",
    "        for sub in subs:\n",
    "            sum += self.getImportance(employees[1:], sub)\n",
    "\n",
    "        return sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        # random access: map\n",
    "        id_2_employee = {}\n",
    "        for employee in employees:\n",
    "            id_2_employee[employee.id] = employee\n",
    "        \n",
    "        # traverse tree and get sum\n",
    "        return self.dfs(id, id_2_employee)\n",
    "\n",
    "    def dfs(self, id: int, id_2_employee: Dict[int, \"Employee\"]) -> int:\n",
    "        if id not in id_2_employee: return 0\n",
    "        cur = id_2_employee[id]\n",
    "        res = cur.importance\n",
    "        for sub_id in cur.subordinates:\n",
    "            res += self.dfs(sub_id, id_2_employee)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ans=0\n",
    "        q=collections.deque()\n",
    "        for s in employees:\n",
    "            if s.id==id:\n",
    "                q.append(s)\n",
    "                ans+=s.importance\n",
    "        while q:\n",
    "            temp=q.popleft()\n",
    "            for t in employees:\n",
    "                if t.id in temp.subordinates:\n",
    "                    q.append(t)\n",
    "                    ans+=t.importance\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        degree= 0\n",
    "        emps = {}\n",
    "        for emp in employees:\n",
    "            emps[emp.id] = emp\n",
    "\n",
    "        stack = deque()\n",
    "        stack.append(id)\n",
    "        while len(stack)>0:\n",
    "            idx = stack.popleft()\n",
    "            emp = emps[idx]\n",
    "            degree += emp.importance\n",
    "            for i in emp.subordinates:\n",
    "                stack.append(i)\n",
    "    \n",
    "        \n",
    "        return degree\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "\n",
    "        def getEmployee(idx):\n",
    "            for employee in employees:\n",
    "                if employee.id == idx:\n",
    "                    return employee \n",
    "        q = []\n",
    "        ans = 0\n",
    "        q.append(getEmployee(id))\n",
    "        print(q)\n",
    "\n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            print(type(node))\n",
    "            ans += node.importance\n",
    "            for index in node.subordinates:\n",
    "                q.append(getEmployee(index)) \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        result = 0\n",
    "        # employees =sorted(employees, key=lambda x:x.id)\n",
    "        employees_map = {emp.id: emp for emp in employees}\n",
    "\n",
    "        # print(list(employees))\n",
    "        from collections import deque\n",
    "        dq = deque()\n",
    "        dq.append(employees_map[id])\n",
    "        while dq:\n",
    "            cur_emp = dq.popleft()\n",
    "            result += cur_emp.importance\n",
    "            if not cur_emp.subordinates:\n",
    "                continue\n",
    "            for sub_id in cur_emp.subordinates:\n",
    "                dq.append(employees_map[sub_id])\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {emp.id: emp for emp in employees}\n",
    "\n",
    "        q = deque([id])\n",
    "        ans = 0\n",
    "        while q:\n",
    "            id = q.popleft()\n",
    "            ans += mp[id].importance\n",
    "            q.extend(mp[id].subordinates)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], idx: int) -> int:\n",
    "        mp = {employee.id: employee for employee in employees}\n",
    "\n",
    "        def dfs(idx: int) -> int:\n",
    "            employee = mp[idx]\n",
    "            total = employee.importance + sum(dfs(subIdx) for subIdx in employee.subordinates)\n",
    "            return total\n",
    "        \n",
    "        return dfs(idx)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hm = defaultdict(list)\n",
    "        for emp in employees:\n",
    "            i,imp,sub = emp.id,emp.importance,emp.subordinates\n",
    "            hm[i] = [imp,sub,False]\n",
    "        ans = 0\n",
    "        queue = [id]\n",
    "        while queue:\n",
    "            temp = queue.pop()\n",
    "            if not hm[temp][2]:\n",
    "                ans += hm[temp][0]\n",
    "                hm[temp][2] = True\n",
    "            for e in hm[temp][1]:\n",
    "                queue.append(e)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp={employee.id:employee for employee in employees}\n",
    "        def dfs(idx):\n",
    "            employee=mp[idx]\n",
    "            ans=employee.importance+sum(dfs(subidx) for subidx in employee.subordinates)\n",
    "            return ans\n",
    "        return dfs(id)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        queue=[id]\n",
    "        importance=0\n",
    "        while len(queue)>0:\n",
    "            for emp in employees:\n",
    "                if emp.id in queue:\n",
    "                    importance+=emp.importance\n",
    "                    for sube in emp.subordinates:\n",
    "                        queue.append(sube)\n",
    "                    queue.remove(emp.id)\n",
    "        return importance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {employee.id: employee for employee in employees}\n",
    "        stack = collections.deque()\n",
    "        stack.append(id)\n",
    "        ans = 0\n",
    "        while(stack):\n",
    "            cur_len = len(stack)\n",
    "            for i in range(cur_len):\n",
    "                cur_idx = stack.popleft()\n",
    "                ans += mp[cur_idx].importance\n",
    "                for j in range(len(mp[cur_idx].subordinates)):\n",
    "                    stack.append(mp[cur_idx].subordinates[j])\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        res = 0\n",
    "        for i in employees:\n",
    "            if id == i.id:\n",
    "                res += i.importance\n",
    "                for j in range(len(i.subordinates)):\n",
    "                    res += self.getImportance(employees,i.subordinates[j])\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List[\"Employee\"], id: int) -> int:\n",
    "        map = {e.id: e for e in employees}\n",
    "\n",
    "        queue = [id]\n",
    "        res = 0\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            res += map[cur].importance\n",
    "            queue.extend(map[cur].subordinates)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hashmap = {}\n",
    "        for employee in employees:\n",
    "            hashmap[employee.id] = employee\n",
    "        queue = [id]\n",
    "        sum = 0\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            e = hashmap[cur]\n",
    "            sum += e.importance\n",
    "            for subordinate in e.subordinates:\n",
    "                queue.append(subordinate)\n",
    "        return sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        m = {}\n",
    "        for i in employees:\n",
    "            m[i.id] = [i.importance,i.subordinates]\n",
    "        que = [id]\n",
    "        ans = 0\n",
    "        while que:\n",
    "            tmp = m[que.pop()]\n",
    "            ans += tmp[0]\n",
    "            for i in tmp[1]:\n",
    "                que.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        dic_employees = {}\n",
    "        for employee in employees:\n",
    "            dic_employees[employee.id] = [employee.importance, employee.subordinates]\n",
    "        result = 0\n",
    "        que = [(id, dic_employees[id])]\n",
    "        while que:\n",
    "            weight, ids = que.pop(0)[1]\n",
    "            result += weight\n",
    "            if ids:\n",
    "                for e in ids:\n",
    "                    que.append((e, dic_employees[e]))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], idx: int) -> int:\n",
    "        mp = {employee.id: employee for employee in employees}\n",
    "\n",
    "        def dfs(idx: int) -> int:\n",
    "            employee = mp[idx]\n",
    "            total = employee.importance + sum(dfs(subIdx) for subIdx in employee.subordinates)\n",
    "            return total\n",
    "\n",
    "        return dfs(idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        cur={}#临时LIST\n",
    "        if employees is None:\n",
    "            return 0\n",
    "        sum=0\n",
    "        for i in employees:\n",
    "            cur[i.id]=i\n",
    "        queue=[id]\n",
    "        while queue:#判断queue是否为空，不为空则取出\n",
    "            temp=queue.pop()\n",
    "            e=cur[temp]\n",
    "            sum+=e.importance\n",
    "            for j in e.subordinates:\n",
    "                queue.append(j)\n",
    "        return sum\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        id_importance_dict = dict()\n",
    "        id_neighbor_dict = dict()\n",
    "        for employee in employees:\n",
    "            id_importance_dict[employee.id] = employee.importance\n",
    "            id_neighbor_dict[employee.id] = employee.subordinates\n",
    "        return importance_calculation(id_importance_dict, id_neighbor_dict, id)\n",
    "\n",
    "def importance_calculation(id_importance_dict, id_neighbor_dict, id):\n",
    "    importance = id_importance_dict[id]\n",
    "    for neighbor in id_neighbor_dict[id]:\n",
    "        importance += importance_calculation(id_importance_dict, id_neighbor_dict, neighbor)\n",
    "    return importance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        imp_dict = {}\n",
    "        sub_dict = {}\n",
    "        visited = set()\n",
    "        for emp in employees:\n",
    "            imp_dict[emp.id] = emp.importance\n",
    "            sub_dict[emp.id] = emp.subordinates\n",
    "        \n",
    "        queue = [id]\n",
    "        visited.add(id)\n",
    "        res = imp_dict[id]\n",
    "        while len(queue):\n",
    "            cur = queue.pop(0)\n",
    "            for sub_id in sub_dict[cur]:\n",
    "                if not sub_id in visited:\n",
    "                    queue.append(sub_id)\n",
    "                    visited.add(sub_id)\n",
    "                    res += imp_dict[sub_id]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def dfs(i):\n",
    "            self.res += w[i]\n",
    "            for j in p2c[i]:\n",
    "                dfs(j)\n",
    "        \n",
    "        w = {}\n",
    "        p2c = collections.defaultdict(set)\n",
    "        for emp in employees:\n",
    "            w[emp.id] = emp.importance\n",
    "            p2c[emp.id] = emp.subordinates\n",
    "        self.res = 0\n",
    "        dfs(id)\n",
    "        return self.res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            for j in range(len(employees)):\n",
    "                if employees[j].id == i:\n",
    "                    nonlocal ans\n",
    "                    ans += employees[j].importance\n",
    "                    for k in range(len(employees[j].subordinates)):\n",
    "                        dfs(employees[j].subordinates[k])\n",
    "        dfs(id)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        m = defaultdict(list)\n",
    "\n",
    "        for e in employees:\n",
    "            m[e.id] = e\n",
    "        \n",
    "        q = deque([id])\n",
    "        res = 0\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                _id = q.popleft()\n",
    "                e = m[_id]\n",
    "                res += e.importance\n",
    "                for sub in e.subordinates:\n",
    "                    q.append(sub)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        for i in range(len(employees)):\n",
    "            d[employees[i].id] = employees[i]\n",
    "        def dfs(i):\n",
    "                nonlocal ans\n",
    "                ans += d[i].importance\n",
    "                for k in range(len(d[i].subordinates)):\n",
    "                    dfs(d[i].subordinates[k])\n",
    "        dfs(id)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {employee.id: employee for employee in employees}\n",
    "        def dfs(idx):\n",
    "            employee = mp[idx]\n",
    "            total = employee.importance + sum(dfs(subidx) for subidx in employee.subordinates)\n",
    "            return total\n",
    "        return dfs(id)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        #importance是重要度,subordinates是直系下属的ID\n",
    "        #层次遍历,广度优先搜索\n",
    "        #队列\n",
    "        hashmap={}\n",
    "        for employee in employees:\n",
    "            hashmap[employee.id]=employee\n",
    "            #通过员工ID找到的员工在数组中的位置\n",
    "        queue=[id]#员工的ID加入队列\n",
    "        sum=0#重要度的和\n",
    "        while queue:\n",
    "            n=queue.pop(0)#弹出队列顶端的元素\n",
    "            e=hashmap[n]\n",
    "            #根据n的值在哈希表中获取员工的相关数组\n",
    "            #【员工id,重要度importance,【直系下属ID】】\n",
    "            sum+=e.importance#获取重要度相加\n",
    "            #搜索员工数组的直系下属的ID,逐个添加,然后进入循环\n",
    "            for subordinate in e.subordinates:\n",
    "                queue.append(subordinate)\n",
    "        return sum\n",
    "                \n",
    "\n",
    "       \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        for i, item in enumerate(employees):\n",
    "            if item.id == id:\n",
    "                ans = item.importance\n",
    "                \n",
    "                for j in item.subordinates:\n",
    "                    ans += self.getImportance(employees, j)\n",
    "                break\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        employee_book = {employee.id : employee for employee in employees}\n",
    "\n",
    "        def sumup_importance(id: int) -> int:\n",
    "            \"\"\"\n",
    "            given an id, return the employee and all subordinate's importance sum\n",
    "            \"\"\"\n",
    "            curr_employee = employee_book[id]\n",
    "            return curr_employee.importance + sum(sumup_importance(id) for id in curr_employee.subordinates)\n",
    "        \n",
    "        return sumup_importance(id)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hashmap = {}\n",
    "        for employee in employees:\n",
    "            hashmap[employee.id] = employee\n",
    "        def Recursion(id):\n",
    "            sum = hashmap[id].importance\n",
    "            for subordinate in hashmap[id].subordinates:\n",
    "                sum += Recursion(subordinate)\n",
    "            return sum\n",
    "        return Recursion(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        from collections import Counter \n",
    "        from collections import defaultdict\n",
    "        from collections import deque\n",
    "        重要性=0\n",
    "        走过的路=Counter()\n",
    "        自身重要性=Counter()\n",
    "        邻接表=defaultdict(list)\n",
    "        for i in employees:\n",
    "            邻接表[i.id]=i.subordinates\n",
    "            自身重要性[i.id]=i.importance\n",
    "        队列=deque()\n",
    "        队列.append(id) \n",
    "        while 队列:\n",
    "            当前节点=队列.popleft()\n",
    "            走过的路[当前节点]=1\n",
    "            重要性+=自身重要性[当前节点]\n",
    "            for i in 邻接表[当前节点]:\n",
    "                if 走过的路[i]==0:\n",
    "                    队列.append(i)\n",
    "        return     重要性    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        queue = collections.deque([id])\n",
    "        res = 0\n",
    "        while queue:\n",
    "            print(queue)\n",
    "            id = queue.popleft()\n",
    "            for employee in employees:\n",
    "                if employee.id == id:\n",
    "                    for j in employee.subordinates:\n",
    "                        queue.append(j)\n",
    "                    res += employee.importance\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        id_to_employee = {}\n",
    "        for employee in employees:\n",
    "            id_to_employee[employee.id] = employee\n",
    "\n",
    "        res = id_to_employee[id].importance\n",
    "        used = set([id])\n",
    "\n",
    "        next_level = id_to_employee[id].subordinates\n",
    "        while len(next_level) > 0:\n",
    "            new_next_level = []\n",
    "\n",
    "            for employee_id in next_level:\n",
    "                if employee_id in used:\n",
    "                    continue\n",
    "                used.add(employee_id)\n",
    "\n",
    "                res += id_to_employee[employee_id].importance\n",
    "                new_next_level += id_to_employee[employee_id].subordinates\n",
    "            \n",
    "            next_level = new_next_level\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        score  = defaultdict(int)\n",
    "\n",
    "        for e in employees:\n",
    "            score[e.id] = e.importance\n",
    "            graph[e.id] = e.subordinates\n",
    "        \n",
    "        q = deque([id])\n",
    "        res = 0\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                _id = q.popleft()\n",
    "                res += score[_id]\n",
    "                for sub in graph[_id]:\n",
    "                    q.append(sub)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        d = {}\n",
    "        for e in employees:\n",
    "            d[e.id] = [e.importance,e.subordinates]\n",
    "        q = [id]\n",
    "        s = 0\n",
    "        while len(q) > 0:\n",
    "            a = q[0]\n",
    "            q.pop(0)\n",
    "            s += d[a][0]\n",
    "            q += d[a][1]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        emp = {e.id: e for e in employees}\n",
    "        def getval(i: int) -> int:\n",
    "            return emp[i].importance + sum(getval(j) for j in emp[i].subordinates)\n",
    "        return getval(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        record = dict()\n",
    "\n",
    "        for employee in employees:\n",
    "            record[employee.id] = (employee.importance, employee.subordinates)\n",
    "\n",
    "        res = 0\n",
    "        queue = deque([id])\n",
    "        while queue:\n",
    "            curr = queue.popleft()\n",
    "            res += record[curr][0]\n",
    "            queue.extend(record[curr][1])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hashmap = {}\n",
    "        for employee in employees:\n",
    "            hashmap[employee.id] = employee\n",
    "        q = [id]\n",
    "        vis = set(q)\n",
    "        res = 0\n",
    "        while q:\n",
    "            id = q.pop(0)\n",
    "            res += hashmap[id].importance\n",
    "            for id_sub in hashmap[id].subordinates:\n",
    "                if id_sub not in vis:\n",
    "                    vis.add(id_sub)\n",
    "                    q.append(id_sub)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for Employee.\r\n",
    "\"\"\"\r\n",
    "# class Node:\r\n",
    "#     def __init__(self,id,val) -> None:\r\n",
    "#         self.id=id\r\n",
    "#         self.val=val\r\n",
    "#         self.nodes=[]\r\n",
    "class Solution:\r\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\r\n",
    "        nodes={}\r\n",
    "        for em in employees:\r\n",
    "            nodes[em.id]=em\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        queue=[id]\r\n",
    "        while queue:\r\n",
    "            idx=queue.pop()\r\n",
    "            ret+=nodes[idx].importance\r\n",
    "            queue.extend(nodes[idx].subordinates)\r\n",
    "        return ret\r\n",
    "    \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    imp = 0\n",
    "    def sol(self, employees, id):\n",
    "        self.imp += employees[id].importance\n",
    "        if employees[id].subordinates == []:\n",
    "            return\n",
    "        for employeeId in employees[id].subordinates:\n",
    "            self.sol(employees, employeeId)\n",
    "            \n",
    "    def getImportance(self, employees: list['Employee'], id: int) -> int:\n",
    "        employees_dict = {employee.id: employee for employee in employees}\n",
    "        self.sol(employees_dict, id)\n",
    "        return self.imp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        d = {e.id:e for e in employees}\n",
    "        index = d[id]\n",
    "        res = 0 #d[id].importance\n",
    "        \n",
    "\n",
    "        quene = [d[id]]\n",
    "        # bfs\n",
    "        while len(quene)>0:\n",
    "            next_quene = []\n",
    "            for e in quene:\n",
    "                res+=e.importance # importance\n",
    "                for child_id in e.subordinates:\n",
    "                    next_quene.append(d[child_id])\n",
    "            quene = next_quene\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        mp = {e.id : e for e in employees}\n",
    "        def dfs(id):\n",
    "            e = mp[id]\n",
    "            return e.importance + sum(dfs(sid) for sid in e.subordinates)\n",
    "        return dfs(id)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        d = collections.defaultdict(tuple)\n",
    "        for emp in employees:\n",
    "            d[emp.id] = (emp.importance, emp.subordinates)\n",
    "        \n",
    "        ret = 0\n",
    "        l = [id]\n",
    "        while l:\n",
    "            emp = d[l.pop()]\n",
    "            ret += emp[0]\n",
    "            for sub_id in emp[1]:\n",
    "                l.append(sub_id)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        employees_dict = {employee.id: employee for employee in employees}\n",
    "\n",
    "        def dfs(required_id):\n",
    "            employee = employees_dict[required_id]\n",
    "            return employee.importance + sum([dfs(i) for i in employee.subordinates])\n",
    "\n",
    "        return dfs(id)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        tmp=[id]\n",
    "        res=0\n",
    "        dic={}\n",
    "\n",
    "        for i  in range(len(employees)):\n",
    "            e=employees[i]\n",
    "            dic[e.id]=i\n",
    "\n",
    "        while tmp:\n",
    "            idx=tmp.pop()\n",
    "            ee=employees[dic[idx]]\n",
    "            res+=ee.importance\n",
    "            tmp+=ee.subordinates\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        employee_dict = {employee.id: employee for employee in employees}\n",
    "      \n",
    "        def dfs(id:int):\n",
    "            em = employee_dict[id]\n",
    "            return em.importance + sum(dfs(x) for x in em.subordinates)\n",
    "        return dfs(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ip = {}\n",
    "        sp = {}\n",
    "        p = collections.defaultdict(int)\n",
    "        for k, v in enumerate(employees):\n",
    "            ip[v.id] = v.importance\n",
    "            sp[v.id] = v.subordinates\n",
    "        \n",
    "        def dfs(id):\n",
    "            p[id] = ip[id]\n",
    "            if not sp[id]:\n",
    "                return p[id]\n",
    "            \n",
    "            for s in sp[id]:\n",
    "                p[id] += dfs(s)\n",
    "            \n",
    "            return p[id]\n",
    "        \n",
    "        return dfs(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ip = {}\n",
    "        sp = {}\n",
    "        p = collections.defaultdict(int)\n",
    "        for k, v in enumerate(employees):\n",
    "            ip[v.id] = v.importance\n",
    "            sp[v.id] = v.subordinates\n",
    "        \n",
    "        def dfs(id):\n",
    "            p[id] = ip[id]\n",
    "            if not sp[id]:\n",
    "                return p[id]\n",
    "            \n",
    "            for s in sp[id]:\n",
    "                p[id] += dfs(s)\n",
    "            \n",
    "            return p[id]\n",
    "        \n",
    "        return dfs(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        dic={}\n",
    "        for i in employees:\n",
    "            dic[i.id]=[i.importance,i.subordinates]\n",
    "        queue=deque([id])\n",
    "        ans=dic[id][0]\n",
    "        while queue:\n",
    "            id=queue.popleft()\n",
    "            for i in dic[id][1]:\n",
    "                queue.append(i)\n",
    "                ans+=dic[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        emp=[None]*2000\n",
    "        for p in employees:\n",
    "            emp[p.id]=[p.id,p.importance,p.subordinates]\n",
    "        d=defaultdict(int)\n",
    "        def calc_import(id):\n",
    "            if not d[id]:\n",
    "                temp=emp[id][1]\n",
    "                for id_ in emp[id][2]:temp+=calc_import(id_)\n",
    "                d[id]=temp\n",
    "            return d[id]\n",
    "        return calc_import(id)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        id_to_importance = {}\n",
    "        id_to_subordinates = {}\n",
    "        for employee in employees:\n",
    "            id_to_importance[employee.id] = employee.importance\n",
    "            id_to_subordinates[employee.id] = employee.subordinates\n",
    "\n",
    "        q = [id]\n",
    "        res = 0\n",
    "        \n",
    "        while len(q) > 0:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                tmp_id = q.pop()\n",
    "                res += id_to_importance[tmp_id]\n",
    "                q += id_to_subordinates[tmp_id]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ans = 0\n",
    "        mp = {x.id : x for x in employees}\n",
    "        q = [id]\n",
    "        # print(f'{q}')\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x in q:\n",
    "                ans += mp[x].importance\n",
    "                for sub in mp[x].subordinates:\n",
    "                    nq.append(sub)\n",
    "            q = nq\n",
    "\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        tbl = {} \n",
    "        for employee in employees:\n",
    "            tbl[employee.id] = employee\n",
    "\n",
    "        res = 0\n",
    "        def calculate(employee):\n",
    "            nonlocal res\n",
    "            res += employee.importance\n",
    "            for childId in employee.subordinates:\n",
    "                if childId in tbl:\n",
    "                    calculate(tbl[childId])\n",
    "        \n",
    "        if id in tbl:\n",
    "            calculate(tbl[id])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        ha_dict = {employee.id : employee for employee in employees}\n",
    "\n",
    "        def dfs(idx):\n",
    "            employee = ha_dict[idx]\n",
    "            total = employee.importance + sum(dfs(subidx) for subidx in employee.subordinates)\n",
    "            return total\n",
    "        return dfs(id)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        hash_data = {}\n",
    "        for i in employees:\n",
    "            hash_data[i.id] = (i.importance,i.subordinates)\n",
    "        que = [id]\n",
    "        res = 0\n",
    "        while(len(que)!=0):\n",
    "            temp = que.pop(0)\n",
    "            temp = hash_data[temp]\n",
    "            # print(temp)\n",
    "            res+=temp[0]\n",
    "            for index in temp[1]:\n",
    "                que.append(index)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for Employee.\n",
    "class Employee:\n",
    "    def __init__(self, id: int, importance: int, subordinates: List[int]):\n",
    "        self.id = id\n",
    "        self.importance = importance\n",
    "        self.subordinates = subordinates\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getImportance(self, employees: List['Employee'], id: int) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        n=len(employees)\n",
    "        value=[0]*(2001)\n",
    "        #print(employees)\n",
    "        for tp in employees:\n",
    "            a,b,ls=tp.id,tp.importance,tp.subordinates\n",
    "            #print(a,b,ls)\n",
    "            value[a]=b\n",
    "            for c in ls:\n",
    "                e[a].append(c)\n",
    "        #print(e)\n",
    "        q=collections.deque()\n",
    "        q.append(id)\n",
    "        ret=0\n",
    "        \n",
    "        while q:\n",
    "            tp=q.popleft()\n",
    "            ret+=value[tp]\n",
    "            for i in e[tp]:\n",
    "                q.append(i)\n",
    "                \n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
